{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost Homecoming of a Robot in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格图中机器人回家的最小代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的网格图，其中&nbsp;<code>(0, 0)</code>&nbsp;是最左上角的格子，<code>(m - 1, n - 1)</code>&nbsp;是最右下角的格子。给你一个整数数组&nbsp;<code>startPos</code>&nbsp;，<code>startPos = [start<sub>row</sub>, start<sub>col</sub>]</code>&nbsp;表示 <strong>初始</strong>&nbsp;有一个 <strong>机器人</strong>&nbsp;在格子&nbsp;<code>(start<sub>row</sub>, start<sub>col</sub>)</code>&nbsp;处。同时给你一个整数数组&nbsp;<code>homePos</code>&nbsp;，<code>homePos = [home<sub>row</sub>, home<sub>col</sub>]</code>&nbsp;表示机器人的 <strong>家</strong>&nbsp;在格子&nbsp;<code>(home<sub>row</sub>, home<sub>col</sub>)</code>&nbsp;处。</p>\n",
    "\n",
    "<p>机器人需要回家。每一步它可以往四个方向移动：<strong>上</strong>，<strong>下</strong>，<strong>左</strong>，<strong>右</strong>，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从&nbsp;<strong>0</strong>&nbsp;开始的额整数数组：长度为&nbsp;<code>m</code>&nbsp;的数组&nbsp;<code>rowCosts</code> &nbsp;和长度为 <code>n</code>&nbsp;的数组&nbsp;<code>colCosts</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果机器人往 <strong>上</strong>&nbsp;或者往 <strong>下</strong>&nbsp;移动到第 <code>r</code>&nbsp;<strong>行</strong>&nbsp;的格子，那么代价为&nbsp;<code>rowCosts[r]</code>&nbsp;。</li>\n",
    "\t<li>如果机器人往 <strong>左</strong>&nbsp;或者往 <strong>右</strong>&nbsp;移动到第 <code>c</code>&nbsp;<strong>列</strong> 的格子，那么代价为&nbsp;<code>colCosts[c]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回机器人回家需要的 <strong>最小总代价</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/11/eg-1.png\" style=\"width: 282px; height: 217px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]\n",
    "<b>输出：</b>18\n",
    "<b>解释：</b>一个最优路径为：\n",
    "从 (1, 0) 开始\n",
    "-&gt; 往下走到 (<em><strong>2</strong></em>, 0) 。代价为 rowCosts[2] = 3 。\n",
    "-&gt; 往右走到 (2, <em><strong>1</strong></em>) 。代价为 colCosts[1] = 2 。\n",
    "-&gt; 往右走到 (2, <em><strong>2</strong></em>) 。代价为 colCosts[2] = 6 。\n",
    "-&gt; 往右走到 (2, <em><strong>3</strong></em>) 。代价为 colCosts[3] = 7 。\n",
    "总代价为 3 + 2 + 6 + 7 = 18</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>机器人已经在家了，所以不需要移动。总代价为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == rowCosts.length</code></li>\n",
    "\t<li><code>n == colCosts.length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= rowCosts[r], colCosts[c] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>startPos.length == 2</code></li>\n",
    "\t<li><code>homePos.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>row</sub>, home<sub>row</sub> &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>col</sub>, home<sub>col</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-homecoming-of-a-robot-in-a-grid](https://leetcode.cn/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-homecoming-of-a-robot-in-a-grid](https://leetcode.cn/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0]\\n[2,3]\\n[5,4,3]\\n[8,2,6,7]', '[0,0]\\n[0,0]\\n[5]\\n[26]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x, y = startPos\n",
    "        X, Y = homePos\n",
    "        ans = sum(rowCosts[x+1:X+1]) if x < X else sum(rowCosts[X:x])\n",
    "        ans += sum(colCosts[y+1:Y+1]) if y < Y else sum(colCosts[Y:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        m = len(rowCosts)\n",
    "        n = len(colCosts)\n",
    "        sx,sy = startPos\n",
    "        tx,ty = homePos\n",
    "        if sx==tx and sy==ty:\n",
    "            return 0\n",
    "        smallx = sx if sx<tx else tx\n",
    "        largex = tx if sx<tx else sx\n",
    "        smally = sy if sy<ty else ty\n",
    "        largey = ty if sy<ty else sy\n",
    "        res = 0\n",
    "        if largex!=smallx:\n",
    "            for i in range(smallx+1, largex):\n",
    "                res += rowCosts[i]\n",
    "            res += rowCosts[tx]\n",
    "        if largey!=smally:\n",
    "            for i in range(smally+1, largey):\n",
    "                res += colCosts[i]\n",
    "            res += colCosts[ty]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        minx, maxx = min(startPos[0], homePos[0]), max(startPos[0], homePos[0])\n",
    "        miny, maxy = min(startPos[1], homePos[1]), max(startPos[1], homePos[1])\n",
    "        ret = sum(rowCosts[i] for i in range(minx, maxx + 1)) + sum(colCosts[i] for i in range(miny, maxy + 1))\n",
    "        return ret - rowCosts[startPos[0]] - colCosts[startPos[1]]\n",
    "        \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if startPos[0] < homePos[0]:res += sum(rowCosts[startPos[0] + 1:homePos[0] + 1])\n",
    "        else: res += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] < homePos[1]:res += sum(colCosts[startPos[1] + 1:homePos[1] + 1])\n",
    "        else: res += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        \n",
    "        return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0 = startPos\n",
    "        x1, y1= homePos\n",
    "        ans = -rowCosts[x0] - colCosts[y0]\n",
    "        if x0 > x1:\n",
    "            x0, x1 = x1, x0\n",
    "        if y0 > y1:\n",
    "            y0, y1 = y1, y0\n",
    "        for cost in rowCosts[x0:x1+1]:\n",
    "            ans += cost\n",
    "        for cost in colCosts[y0:y1+1]:\n",
    "            ans += cost\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        return sum(rowCosts[x] for x in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0]) + 1)) \\\n",
    "         + sum(colCosts[x] for x in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1]) + 1)) \\\n",
    "         - rowCosts[startPos[0]] - colCosts[startPos[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0, x1, y1 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "        ans = -rowCosts[x0] - colCosts[y0] # 初始的行列无需计算\n",
    "        if x0 > x1: \n",
    "            x0, x1 = x1, x0 # 交换位置，保证 x0 <= x1\n",
    "        if y0 > y1: \n",
    "            y0, y1 = y1, y0 # 交换位置，保证 y0 <= y1\n",
    "        for cost in rowCosts[x0 : x1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        for cost in colCosts[y0 : y1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if startPos[0] != homePos[0]:\n",
    "            if startPos[0] < homePos[0]:\n",
    "                ans += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "            else:\n",
    "                ans += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] != homePos[1]:\n",
    "            if startPos[1] < homePos[1]:\n",
    "                ans += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "            else:\n",
    "                ans += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        si, sj = startPos\n",
    "        ei, ej = homePos\n",
    "        \n",
    "        si, ei = (si, ei) if si <= ei else (ei, si)\n",
    "        sj, ej = (sj, ej) if sj <= ej else (ej, sj)\n",
    "\n",
    "        return (\n",
    "            sum(rowCosts[si:ei + 1])\n",
    "            + sum(colCosts[sj:ej + 1])\n",
    "            - rowCosts[startPos[0]]\n",
    "            - colCosts[startPos[1]]\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # 代价都是正的，所以不可绕路\n",
    "        # 贪心找x, y 较小分量即可\n",
    "        x1, y1, x2, y2 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "\n",
    "        ans = -rowCosts[x1] - colCosts[y1]\n",
    "        # 水平移动代价\n",
    "        if x1 > x2:\n",
    "            x1, x2 = x2, x1\n",
    "        for i in range(x1, x2+1):\n",
    "            ans += rowCosts[i]\n",
    "        \n",
    "        # 垂直移动代价\n",
    "        if y1 > y2:\n",
    "            y1, y2 = y2, y1\n",
    "        for i in range(y1, y2+1):\n",
    "            ans += colCosts[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        if homePos == startPos:\n",
    "            return 0\n",
    "\n",
    "        st = startPos[0]\n",
    "        flag = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            flag = -1 \n",
    "        cst = 0\n",
    "        while st != homePos[0]:\n",
    "            st += flag\n",
    "            cst += rowCosts[st]\n",
    "\n",
    "        st = startPos[1]\n",
    "        flag = 1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            flag = -1 \n",
    "\n",
    "        while st != homePos[1]:\n",
    "            st += flag\n",
    "            cst += colCosts[st]\n",
    "\n",
    "        return cst        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rmin = min(startPos[0], homePos[0])\n",
    "        rmax = max(startPos[0], homePos[0])\n",
    "        cmin = min(startPos[1], homePos[1])\n",
    "        cmax = max(startPos[1], homePos[1])\n",
    "\n",
    "        ans = sum(rowCosts[rmin:rmax+1]) + sum(colCosts[cmin:cmax+1])\n",
    "        ans -= rowCosts[startPos[0]]\n",
    "        ans -= colCosts[startPos[1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x,y=startPos[0],startPos[1]\n",
    "        a,b=homePos[0],homePos[1]\n",
    "        ans=0\n",
    "        if x<a:\n",
    "            ans+=sum(rowCosts[x+1:a+1])\n",
    "        else:\n",
    "            ans+=sum(rowCosts[a:x])\n",
    "        if y<b:\n",
    "            ans+=sum(colCosts[y+1:b+1])\n",
    "        else:\n",
    "            ans+=sum(colCosts[b:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        startRow, endRow = startPos[0], homePos[0]\n",
    "        startCol, endCol = startPos[1], homePos[1]\n",
    "        ans = 0\n",
    "        if startRow < endRow:\n",
    "            for i in range(startRow + 1, endRow + 1):\n",
    "                ans += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(startRow - 1, endRow - 1, -1):\n",
    "                ans += rowCosts[i]\n",
    "        if startCol < endCol:\n",
    "            for i in range(startCol + 1, endCol + 1):\n",
    "                ans += colCosts[i]\n",
    "        else:\n",
    "            for i in range(startCol - 1, endCol - 1, -1):\n",
    "                ans += colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(list(Solution().getSteps(5,2)))\n",
    "    print(Solution().minCost([5,5] ,[5,2] ,[7,1,3,3,5,3,22,10,23],[5,5,6,2,0,16]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        sx, sy = startPos\n",
    "        hx, hy = homePos\n",
    "        \n",
    "        ans = 0\n",
    "        if sx <= hx:\n",
    "            ans += sum(rowCosts[i] for i in range(sx+1, hx+1))\n",
    "        else:\n",
    "            ans += sum(rowCosts[i] for i in range(hx, sx))\n",
    "        \n",
    "        if sy <= hy:\n",
    "            ans += sum(colCosts[i] for i in range(sy+1, hy+1))\n",
    "        else:\n",
    "            ans += sum(colCosts[i] for i in range(hy, sy))\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0], homePos[0], step):\n",
    "            ans+=rowCosts[i+step]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos == homePos:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        def hp(h, s, costs):\n",
    "            dx = h - s \n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            if dx == 0:\n",
    "                pass\n",
    "            elif dx > 0:\n",
    "                for k in range(s + 1, h + 1):\n",
    "                    ans += costs[k]\n",
    "            else:\n",
    "                for k in range(h, s):\n",
    "                    ans += costs[k]\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return hp(homePos[0], startPos[0], rowCosts) + hp(homePos[1], startPos[1], colCosts)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        dx, dy = 0, 0\n",
    "        if startPos[0] <= homePos[0]:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        \n",
    "        if startPos[1] <= homePos[1]:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        \n",
    "        return sum(rowCosts[i] for i in range(startPos[0] + dx, homePos[0] + dx, dx)) + sum(colCosts[i] for i in range(startPos[1] + dy, homePos[1] + dy, dy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1]+step, homePos[1]+step, step):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_diff = homePos[0] - startPos[0]\n",
    "        col_diff = homePos[1] - startPos[1]\n",
    "        now_pos = startPos\n",
    "        cost = 0\n",
    "        while now_pos != homePos:\n",
    "            if row_diff > 0:\n",
    "                cost += rowCosts[now_pos[0] + 1]\n",
    "                now_pos[0] += 1\n",
    "                row_diff -= 1\n",
    "            elif row_diff < 0:\n",
    "                cost += rowCosts[now_pos[0] - 1]\n",
    "                now_pos[0] -= 1\n",
    "                row_diff += 1\n",
    "\n",
    "            if col_diff > 0:\n",
    "                cost += colCosts[now_pos[1] + 1]\n",
    "                now_pos[1] += 1\n",
    "                col_diff -= 1\n",
    "            elif col_diff < 0:\n",
    "                cost += colCosts[now_pos[1] - 1]\n",
    "                now_pos[1] -= 1\n",
    "                col_diff += 1\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if s[0] <= h[0]:\n",
    "            for i in range(min(s[0],h[0])+1,max(s[0],h[0])+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(s[0]-1,h[0]-1,-1):\n",
    "                res += rowCosts[i]\n",
    "        if s[1] <= h[1]:\n",
    "            for i in range(min(s[1],h[1])+1,max(s[1],h[1])+1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(s[1]-1,h[1]-1,-1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos[0]>homePos[0]:\n",
    "            dx=-1\n",
    "        else:\n",
    "            dx=1\n",
    "        if startPos[1]>homePos[1]:\n",
    "            dy=-1\n",
    "        else:\n",
    "            dy=1\n",
    "        ans=0\n",
    "        for i in range(startPos[0]+dx, homePos[0]+dx, dx):\n",
    "            ans+=rowCosts[i]\n",
    "        for i in range(startPos[1]+dy, homePos[1]+dy, dy):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rs: List[int], cs: List[int]) -> int:\n",
    "        if s[0] == h[0] and s[1] == h[1]:\n",
    "            return 0\n",
    "        r, c = len(rs), len(cs)\n",
    "        \n",
    "        ans = 0\n",
    "        row_s, row_e = s[0], h[0]\n",
    "        if row_s >= row_e:\n",
    "            for i in range(row_s-1, row_e-1,-1):\n",
    "                ans += rs[i]\n",
    "        else:\n",
    "            for i in range(row_s+1, row_e+1):\n",
    "                ans += rs[i]\n",
    "\n",
    "        col_s, col_e = s[1], h[1]\n",
    "        if col_s >= col_e:\n",
    "            for i in range(col_s-1, col_e-1,-1):\n",
    "                ans += cs[i]\n",
    "        else:\n",
    "            for i in range(col_s+1, col_e+1):\n",
    "                ans += cs[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans1=0\n",
    "        ans2=0\n",
    "        if startPos==homePos:\n",
    "            return 0\n",
    "        while startPos[0]!=homePos[0]:\n",
    "            if startPos[0]>homePos[0]:\n",
    "                startPos[0]-=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "            if startPos[0]<homePos[0]:\n",
    "                startPos[0]+=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "        while startPos[1]!=homePos[1]:\n",
    "            if startPos[1]>homePos[1]:\n",
    "                startPos[1]-=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "            if startPos[1]<homePos[1]:\n",
    "                startPos[1]+=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "        return (ans1+ans2)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        x1, y1 = startPos\n",
    "        x2, y2 = homePos\n",
    "        res = 0\n",
    "        if x1 <= x2:\n",
    "            for i in range(x1+1, x2+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(x2, x1):\n",
    "                res += rowCosts[i]\n",
    "        if y1 <= y2:\n",
    "            for j in range(y1+1, y2+1):\n",
    "                res += colCosts[j]\n",
    "        else:\n",
    "            for j in range(y2, y1):\n",
    "                res += colCosts[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_delta = col_delta = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            row_delta = -1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            col_delta = -1\n",
    "        \n",
    "        res = 0\n",
    "        for index in range(startPos[0] + row_delta, homePos[0] + row_delta, row_delta):\n",
    "            res += rowCosts[index]\n",
    "        for index in range(startPos[1] + col_delta, homePos[1] + col_delta, col_delta):\n",
    "            res += colCosts[index]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # dfs(i,j)从i，j到达终点的最小代价\n",
    "        # 因为cost都是正数，如果又绕过来l肯定代价会更大\n",
    "        sx,sy,tx,ty=startPos[0],startPos[1],homePos[0],homePos[1]\n",
    "        res=0\n",
    "        if sx<tx:\n",
    "            for row in range(sx+1,tx+1):\n",
    "                res+=rowCosts[row]\n",
    "        elif sx>tx:\n",
    "            for row in range(sx-1,tx-1,-1):\n",
    "                res+=rowCosts[row]\n",
    "        if sy<ty:\n",
    "            for row in range(sy+1,ty+1):\n",
    "                res+=colCosts[row]\n",
    "        elif sy>ty:\n",
    "            for row in range(sy-1,ty-1,-1):\n",
    "                res+=colCosts[row]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rs = 0\n",
    "        for i in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0])+1):\n",
    "            rs += rowCosts[i]\n",
    "        for j in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1])+1):\n",
    "            rs += colCosts[j]\n",
    "        return rs-colCosts[startPos[1]]-rowCosts[startPos[0]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0  # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        y1, x1 = startPos\n",
    "        y2, x2 = homePos\n",
    "        if y1 <= y2:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        if x1 <= x2:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        ret = sum(rowCosts[y] for y in range(y1+dy, y2+dy, dy))\n",
    "        ret += sum(colCosts[x] for x in range(x1+dx, x2+dx, dx))\n",
    "        return ret\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
